#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctime>

#define N 10
//六大排序
typedef int ElemType;
typedef struct SSTable {
    ElemType lenth;
    ElemType *str;
} SSTable;

//初始化顺序表
void ST_Init(SSTable &T, int len) {
    T.lenth = len;
    T.str = (ElemType *) malloc(sizeof(ElemType) * T.lenth);
    int i;
    srand(time(NULL));
    for (i = 0; i < T.lenth; i++) {
        T.str[i] = rand() % 100;//随机数范围（0~99）
    }
}

void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

void array_print(SSTable T) {
    for (int i = 0; i < T.lenth; i++) {
        printf("%3d", T.str[i]);
    }
    printf("\n");
}

//冒泡排序
void BubbleSort(ElemType *str, int len) {
    int i, j;
    bool flag;
    for (i = 0; i < len; i++) {
        for (j = len - 1; j > i; j--) {
            flag = false;
            if (str[j] < str[j - 1]) {
                swap(str[j], str[j - 1]);
                flag = true;
            }
        }
        if (!flag) {
            return;
        }
    }


}

//选择排序
void SelectSort(ElemType *str, int len) {
    int i, j, k;
    for (i = 0; i < len - 1; i++) {
        k = i;
        for (j = i + 1; j < len; j++) {
            if (str[k] > str[j]) {
                k = j;
            }
        }
        if (k != i) {
            swap(str[k], str[i]);
        }
    }
}

//插入排序
void InsertSort(ElemType *str, int len) {
    int insertval, i, j;
    for (i = 1; i < len; i++) {
        insertval = str[i];
        for (j = i - 1; j >= 0 && insertval < str[j]; j--) {
            str[j + 1] = str[j];
        }
        str[j + 1] = insertval;
    }
}

//快排中核心(分割函数)
int partition(ElemType *str, int low, ElemType high) {
    int pivot = str[low];//选最左边的第一个值作为分割值
    while (low < high) {
        while (low < high && str[high] >= pivot) high--;
        str[low] = str[high];
        while (low < high && str[low] <= pivot) low++;
        str[high] = str[low];
    }
    str[low] = pivot;
    return low;
}

//快速排序
void QuickSort(ElemType *str, int low, ElemType high) {
    if (low < high) {
        int pivot = partition(str, low, high);
        QuickSort(str, low, pivot - 1);
        QuickSort(str, pivot + 1, high);
    }

}

void AjustDown(ElemType *str, int low, ElemType lenth) {
    int dad = low;//父亲结点
    int son = dad * 2 + 1;//左节点
    while (son < lenth) {
        //左节点和右节点进行比较
        if (son + 1 < lenth && str[son] < str[son + 1]) {
            son++;
        }
        //将两个结点中的较大值跟父亲节点进行比较
        if (str[son] > str[dad]) {
            swap(str[son], str[dad]);
            dad = son;
            son = dad * 2 + 1;
        } else {
            break;
        }
    }
}

//堆排序
void HeapSort(ElemType *str, ElemType lenth) {
    int i;
    //先调整最后一颗子树
    for (i = lenth - 1 / 2; i >= 0; i--) {
        AjustDown(str, i, lenth);
    }
    //将根节点和最后一个结点进行值交换
    swap(str[0], str[lenth - 1]);

    for (i = lenth - 1; i > 1; i--) {
        AjustDown(str, 0, i);
        swap(str[0], str[i - 1]);
    }
}

void Merge(ElemType *str, int low, int mid, ElemType high) {
    static int arr[N];
        int i, j, k;
    for (i = low; i <= high; i++) {
        arr[i] = str[i];
    }
    k = low;
    for (i = low, j = mid + 1; i <= mid && j <= high; k++) {
        if (arr[i] <= arr[j]) {
            str[k] = arr[i++];
        } else {
            str[k] = arr[j++];
        }
    }
    //如果有一方还有剩余，接着放入即可
    while (i <= mid) {
        str[k++] = arr[i++];
    }
    while (j <= high) {
        str[k++] = arr[j++];
    }
}

//归并排序
void MergeSort(ElemType *str, int low, ElemType high) {
    if (low < high) {
        //分
        int mid = (low + high) / 2;
        MergeSort(str, low, mid);
        MergeSort(str, mid + 1, high);
        //合
        Merge(str, low, mid, high);
    }
}

int main() {
    SSTable T;
    ST_Init(T, 10);
    array_print(T);
    /**冒泡排序*/
    BubbleSort(T.str, 10);
    array_print(T);
/**选择排序*/
    SelectSort(T.str, 10);
    array_print(T);
/**插入排序*/
    InsertSort(T.str, 10);
    array_print(T);
/**快速排序*/
    QuickSort(T.str, 0, T.lenth-1);
    array_print(T);
/**堆排序 */
    HeapSort(T.str, T.lenth);
    array_print(T);
/**归并排序*/
    MergeSort(T.str, 0, T.lenth-1);
    array_print(T);
    return 0;
}
